%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% data section
\SetKwData{MyFalse}{False}
%%
%% input
\KwIn{An undirected or directed graph $G = (V, E)$ that is weighted
  and has no self-loops. Negative edge weights are allowed. The order
  of $G$ is $n > 0$. A vertex $s \in V$ from which to start the
  search. Vertices are numbered from 1 to $n$,
  i.e.~$V = \{1, 2, \dots, n\}$.}
%%
%% output
\KwOut{A list $D$ of distances such that $D[v]$ is the distance of a
  shortest path from $s$ to $v$. A list $P$ of vertex parents such
  that $P[v]$ is the parent of $v$, i.e. $v$ is adjacent from
  $P[v]$. If $G$ has negative-weight cycles, then return
  \MyFalse. Otherwise, return $D$ and $P$.}
\BlankLine
%%
%% algorithm body
$D \assign [\infty, \infty, \dots, \infty]$\tcc*[f]{$n$ copies of $\infty$}\nllabel{alg:Bellman_Ford:init_infinity}\;
$D[s] \assign 0$\;
$P \assign [\,]$\nllabel{alg:Bellman_Ford:init_parent_list}\;
\For{$i \assign 1, 2, \dots, n-1$\nllabel{alg:Bellman_Ford:for_loop:relax}}{
  \For{\rm each edge $uv \in E$}{
    \If{$D[v] > D[u] + w(uv)$}{
      $D[v] \assign D[u] + w(uv)$\;
      $P[v] \assign u$\;
    }
  }
  \nllabel{alg:Bellman_Ford:for_loop:end_relax}
}
\For{\rm each edge $uv \in E$\nllabel{alg:Bellman_Ford:for_loop:check_negative_weight_cycles}}{
  \If{$D[v] > D[u] + w(uv)$}{
    \Return \MyFalse\;
  }
}
\Return $(D, P)$\;
